/*
 * @lc app=leetcode.cn id=63 lang=cpp
 * @lcpr version=30204
 *
 * [63] 不同路径 II
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    vector<pair<int,int>> directions = {
        {1, 0},
        {0, 1}
    };
    vector<vector<int>> memo; // 记忆化数组
    int m, n;

    int dfs(int x, int y, vector<vector<int>>& grid) {
        if (x == m-1 && y == n-1) return 1; // 到达终点
        if (memo[x][y] != -1) return memo[x][y]; // 已计算过

        int res = 0;
        for (auto& [dx, dy] : directions) {
            int nx = x + dx, ny = y + dy;
            if (nx < m && ny < n && grid[nx][ny] != 1) { // 检查越界+非障碍物
                res += dfs(nx, ny, grid);
            }
        }
        return memo[x][y] = res;
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        m = obstacleGrid.size();
        if (m == 0) return 0;
        
        n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;
        memo = vector<vector<int>>(m, vector<int>(n, -1));
        
        return dfs(0, 0, obstacleGrid);;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [[0,0,0],[0,1,0],[0,0,0]]\n
// @lcpr case=end

// @lcpr case=start
// [[0,1],[0,0]]\n
// @lcpr case=end

 */

